package com.zjsru.plan2024.oneday;

import java.util.Arrays;

/**
 * 1738. 找出第 K 大的异或坐标值
 * @Author: cookLee
 * @Date: 2024-05-26
 */
public class KthLargestValue {

    /**
     * 主
     * \
     * 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
     * 请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
     * \
     * 输入：matrix = [[5,2],[1,6]], k = 1
     * 输出：7
     * 解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
     * \
     * 输入：matrix = [[5,2],[1,6]], k = 2
     * 输出：5
     * 解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
     * \
     * 输入：matrix = [[5,2],[1,6]], k = 3
     * 输出：4
     * 解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
     * \
     * 输入：matrix = [[5,2],[1,6]], k = 4
     * 输出：0
     * 解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{5,2},{1,6}};
        int k = 1;
        KthLargestValue kthLargestValue = new KthLargestValue();
        System.out.println(kthLargestValue.kthLargestValue(matrix,k));
    }

    /**
     * 第k个最大值
     *
     * @param matrix 矩阵
     * @param k      k
     * @return int
     */
    private int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        //结果数组
        int[] ans = new int[m * n];
        int[][] sum = new int[m + 1][n + 1];
        //最大下标
        int idx = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //由于一个数异或自己等于 0,因此sum[i][j]添加这一部分
                sum[i + 1][j + 1] = sum[i + 1][j] ^ sum[i][j + 1] ^ sum[i][j] ^ matrix[i][j];
                ans[idx] = sum[i + 1][j + 1];
                idx++;
            }
        }
        //排序,方便后续取值
        Arrays.sort(ans);
        return ans[idx - k];
    }

}
